/**
 * 项目名称: Floyd.cpp
 * 项目路径: study/DataStructure/数据结构/图/应用/最短路径
 * 编辑时间: 2024年08月12日09时59分22秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

/**
 * Floyd算法:求每一对顶点之间的最短路径
 * 使用动态规划思想划分为
 * #初始:不允许在其他顶点中转,最短路径是
 * #0:若允许在v0中转,最短路径是
 * #1:若允许在v0,v1中转,最短路径是
 * #2:若允许在v0,v1,v2中转,最短路径是
 * ...
 * #n-1:若允许在v0,v1...vn-1中转,最短路径是
 * @return
 */

const int N = 100010;
int path[N][N];//路径前驱
int g[N][N];//地图
int n;//顶点数
void init() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i == j)g[i][j] = 0;
            else g[i][j] = 0x3f3f3f3f;
            path[i][j] = -1;
        }
}

void Floyd() {
    for (int k = 0; k < n; k++)//中转点
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (g[i][j] > g[i][k] + g[k][j]) {
                    g[i][j] = g[i][k] + g[k][j];
                    path[i][j] = k;
                }
}

int main() {

    return 0;
}
